#include <iostream>
#include <cassert>
using namespace std;


template <typename Graph>
class Component{

private:
    Graph &G;			// 成员变量 存储Graph
    bool *visited;		// 布尔数组存储是否访问过
    int ccount;			// 有多少连通分量
	// 为了判断两个点是否是相连的
    int *id;			// 相连的节点id取相同的值

    void dfs( int v ){

        visited[v] = true;
        id[v] = ccount;			// 初始 ccount=0;
		// 遍历 G这张图 v这个节点
        typename Graph::adjIterator adj(G, v);	// 显式声明是Graph中一个类型
        for( int i = adj.begin() ; !adj.end() ; i = adj.next() ){
            if( !visited[i] )
                dfs(i);
        }
    }

public:
	// 用户传入图的引用
    Component(Graph &graph): G(graph){	// 初始化 G

        visited = new bool[G.V()];		// 开辟V个节点个空间
        id = new int[G.V()];
        ccount = 0;

        for( int i = 0 ; i < G.V() ; i ++ ){
            visited[i] = false;
            id[i] = -1;
        }

		// 遍历图中节点, 未被访问进行一次深度优先遍历
        for( int i = 0 ; i < G.V() ; i ++ )
            if( !visited[i] ){
                dfs(i);
                ccount ++;
            }
    }

    ~Component(){
        delete[] visited;
        delete[] id;
    }

	// 返回一张图有几个连通分量
    int count(){
        return ccount;
    }

	// 判断两个节点是否连通(是否属于同一个连通分量)
	bool isConnected(int v, int w){
		assert(v >= 0 && v < G.V());
		assert(w >= 0 && w < G.V());
		return id[v] == id[w];
	}

};
